/**
 * @Author YuanYuan
 * @Date 2022/7/17
 * @Time 23:09
 */
public class Sort {
    // 插入排序
    public static void insertSort(int[] array){
        // write code  here
        if(array.length == 0) {
            return;
        }
        int i = 0;
        int j = 0;
        for(i = 1;i<array.length;i++){
            int temp = array[i];
            for(j = i-1;j>=0;j--) {
                if(array[j]>temp) {
                    array[j+1] = array[j];
                }else {
                    break;
                }
            }
            array[j+1] = temp;
        }

    }


        // 希尔排序
    public static void shellSort(int[] array,int src){
        // write code  here
        if(array.length == 0) {
            return;
        }
        int i = 0;
        int j = 0;
        for(i = 1;i<array.length;i++){
            int temp = array[i];
            for(j = i-src;j>=0;j-=src) {
                if(array[j]>temp) {
                    array[j+src] = array[j];
                }else {
                    break;
                }
            }
            array[j+src] = temp;
        }
    }
    // 选择排序
    public static void selectSort(int[] array){
        // write code  here
        int min = 0;
        for (int i = 0; i < array.length; i++) {
            min = i;
            for (int j = i+1; j < array.length; j++) {
                if(array[j]<array[min]) {
                    min = j;
                }
            }
            swap(array,min,i);
        }
    }
    public static void selectSort2(int[] array){
        // write code  here
        int left = 0;
        int right = array.length-1;
        while(left<right) {
            int maxIndex = left;
            int minIndex = left;
            for (int i = left+1; i < array.length; i++) {
                if(array[i] < array[minIndex]) {
                    minIndex = i;
                }
                if(array[i]>array[maxIndex]) {
                    maxIndex = i;
                }
            }
            swap(array,left++,minIndex);
            if(left-1 == maxIndex) {
                maxIndex = minIndex;
            }
            swap(array,right--,maxIndex);
        }

    }

    private static void swap(int[] array,int ret1,int ret2) {
        int temp = array[ret1];
        array[ret1] = array[ret2];
        array[ret2] = temp;
    }
    // 堆排序
    public static void creatBigheap(int[] array) {
        for (int parent = (array.length-1-1)/2; parent >=0 ; parent--) {
            downsort(array,parent,array.length);
        }
    }
    private static void downsort(int[] array,int parent,int usesize) {
        int child = (parent*2)+1;
        while(child<usesize) {
            if(child+1<usesize&&array[child]<array[child+1]) {
                child++;
            }
            if(array[parent] < array[child]) {
                swap(array,parent,child);
            }
            parent = child;
            child = child*2+1;
        }
    }
    public static void heapSort(int[] array){
        // write code here
        //先排成大根堆
        creatBigheap(array);
        int end = array.length-1;
        while(end>=0) {
            swap(array,0,end);
            //最大的就在前三个里面呢,只需要从前三个里面找到就行
            downsort(array,0,end);
            end--;
        }
    }
    // 快速
    public static void quick(int[] array,int left,int right){
        // write code  here
        if(right<left) {
            return;
        }
        int prvot = partition(array,left,right);
        quick(array,left,prvot-1);
        quick(array,prvot+1,right);

    }
    public static void quickSort(int[] array){
        // write code  here
        quick(array,0,array.length-1);

    }
    public static void bubbleSort(int[] array){
        // write code  here
        boolean flag = false;
        for (int i = 0; i < array.length-1; i++) {
            for (int j = 0; j < array.length-i-1; j++) {
                if(array[j]>array[j+1]) {
                    swap(array,j,j+1);
                    flag = true;
                }
            }
            if(!flag) {
                break;
            }
        }
    }

    private static int partition(int[] array,int start,int end) {
        int prev = start;
        while(start<end) {
            while(start<end&&array[end]>=array[prev]) {
                end--;
            }
            while(start<end&&array[start]<=array[prev]) {
                start++;
            }
            swap(array,start,end);
        }
        swap(array,prev,start);
        return start;
    }
    // 归并排序---递归
    public static void mergeSort(int[] array,int left,int right){
        // write code  here
        int mid = (left+right)/2;
        if(left>=right) {
            return;
        }
        mergeSort(array,left,mid);
        mergeSort(array,mid+1,right);
        mergeDate(array,left,mid,right);

    }
    public static void mergeDate(int[] array, int left, int mid, int right){
        int[] tem = new int[right-left+1];
        int k = 0;
        int start1 = left;
        int end1 = mid;
        int start2 = mid+1;
        int end2 = right;
       while(start1<=end1&&start2<=end2) {
           if(array[start1]<=array[start2]) {
               tem[k++] = array[start1++];
           }else {
               tem[k++] = array[start2++];
           }
       }
       while (start1<=end1) {
           tem[k++]=array[start1++];
       }
        while (start2<=end2) {
            tem[k++]=array[start2++];
        }

        for (int i = 0; i < k; i++) {
            array[i+left] = tem[i];
        }
    }
    public static void mergeSort(int[] array){
        // write code  here
       // int[] temp = new int[array.length];
        mergeSort(array,0,array.length-1);

    }

// 归并排序---非递归
    public static void mergeSort1(int[] array){
        // write code  here
        int gap = 1;
        int left = 0;
        int right = array.length-1;
        while(gap<array.length) {
            for (int i = 0; i < array.length; i+=gap*2) {
                int start = i;
                int mid = start+gap-1;
                int end = mid+gap;
                if(mid>=array.length) {
                    mid = array.length-1;
                }
                if(end>=array.length) {
                    end = array.length-1;
                }
                mergeDate(array,start,mid,end);
            }
            gap*=2;
        }
    }

// 计数排序
    public static void countSort1(int[] array){
        // write code  here
        int min = array[0];
        int max = array[0];
        for (int i = 0; i < array.length; i++) {
            if(array[i]<min) {
                min = array[i];
            }
            if(array[i]>max) {
                max = array[i];
            }
        }
        int[] count = new int[max-min+1];
        //计数
        for (int i = 0; i < array.length; i++) {
            count[array[i]-min]++;
        }
        //记录i下标
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            while(count[i]!=0) {
                array[index] = i+min;
                count[i]--;
                index++;
            }
        }
    }
}
